﻿//#pragma once
//#include<iostream>
//using namespace std;
//// 枚举值表⽰颜⾊
//enum Colour
//{
//	RED,
//	BLACK
//};
//template<class T>//这里的内容可能是key也可能是pair
//struct RBTreeNode
//{
//	T data;
//	RBTreeNode<T>* _left;
//	RBTreeNode<T>* _right;
//	RBTreeNode<T>* _parent;
//	Colour _col;
//	RBTreeNode(const T& _data) :data(_data), _left(nullptr), _right(nullptr), _parent(nullptr) {}
//};
//
//
//template <class K, class T>
//class RBTree
//{
//	typedef RBTreeNode<T> Node;
//public:
//	Node* Find(const K& key)
//	{
//		Node* cur = _root;
//		while (cur)
//		{
//			if (key > cur->_kv.first)
//			{
//				cur = cur->_right;
//			}
//			else if (key < cur->_kv.first)
//			{
//				cur = cur->_left;
//			}
//			else
//				return cur;
//		}
//		return nullptr;
//	}
//	void RoteR(Node* parent)
//	{
//		Node* prev = parent->_parent;
//		Node* sub = parent;
//		Node* subl = sub->_left;
//		Node* sublr = subl->_right;
//		sub->_left = sublr;
//		if (sublr) sublr->_parent = sub;
//		subl->_right = sub;
//		sub->_parent = subl;
//		
//		if (prev == nullptr)
//		{
//			_root = subl;
//			_root->_parent = nullptr;
//		}
//		else
//		{
//			if (prev->_right == parent)
//			{
//				prev->_right = subl;
//				
//			}
//			else
//			{
//				prev->_left = subl;
//				
//			}
//			subl->_parent = prev;
//		}
//	}
//	void RoteL(Node* parent)
//	{
//		Node* prev = parent->_parent;
//
//		Node* sub = parent;
//		Node* subr = sub->_right;
//		Node* subrl = subr->_left;
//
//		sub->_right = subrl;
//		if (subrl) subrl->_parent = sub;
//		subr->_left = sub;
//		sub->_parent = subr;
//		if (prev == nullptr)
//		{
//			_root = subr;
//			_root->_parent = nullptr;
//		}
//		else
//		{
//			if (prev->_left == parent)
//			{
//				prev->_left = subr;
//				subr->_parent = prev;
//			}
//			else
//			{
//				prev->_right = subr;
//				subr->_parent = prev;
//			}
//		}
//
//	}
//	bool Insert(const pair<K, V>& data)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(data);
//			_root->_col = BLACK;
//			return true;
//		}
//		Node* cur = _root;
//		Node* parent = _root;
//		while (cur)
//		{
//			if (data.first > cur->_kv.first)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (data.first < cur->_kv.first)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		cur = new Node(data);
//		cur->_col = RED;
//		if (parent->_kv.first > data.first)
//		{
//			parent->_left = cur;
//		}
//		else
//		{
//			parent->_right = cur;
//		}
//		cur->_parent = parent;
//		while (parent && parent->_col == RED)
//		{
//			Node* grandfather = parent->_parent;
//			if (grandfather->_left == parent)
//			{
//				Node* uncle = grandfather->_right;
//				if (uncle && uncle->_col == RED)
//				{
//					uncle->_col = parent->_col = BLACK;
//					grandfather->_col = RED;
//
//					cur = grandfather;
//					parent = cur->_parent;
//				}
//				else
//				{
//					if (parent->_left == cur)
//					{
//						RoteR(grandfather);
//						parent->_col = BLACK;
//						grandfather->_col = RED;
//					}
//					else
//					{
//						RoteL(parent);
//						RoteR(grandfather);
//						cur->_col = BLACK;
//						grandfather->_col = RED;
//					}
//					break;
//				}
//			}
//			else
//			{
//				Node* uncle = grandfather->_left;
//				if (uncle && uncle->_col == RED)
//				{
//					uncle->_col = parent->_col = BLACK;
//					grandfather->_col = RED;
//
//					cur = grandfather;
//					parent = cur->_parent;
//				}
//				else
//				{
//					if (parent->_right == cur)
//					{
//						RoteL(grandfather);
//						parent->_col = BLACK;
//						grandfather->_col = RED;
//					}
//					else
//					{
//						RoteR(parent);
//						RoteL(grandfather);
//						cur->_col = BLACK;
//						grandfather->_col = RED;
//					}
//					break;
//				}
//			}
//		}
//		_root->_col = BLACK;//防止一直向上处理到parent是空时
//		return true;
//	}
//
//	int Height()
//	{
//		 return _height(_root);
//	}
//	int Size()
//	{
//		return _size(_root);
//	}
//private:
//	void _inorder(Node* root)
//	{
//		if (root == nullptr) return;
//		_inorder(root->_left);
//		cout << root->_kv.first << ":" << root->_kv.second << endl;
//		_inorder(root->_right);
//	}
//	int _height(Node* root)
//	{
//		if (root == nullptr) return 0;
//		int left = _height(root->_left);
//		int right = _height(root->_right);
//		return left > right ? left + 1: right + 1;
//	}
//	int _size(Node* root)
//	{
//		if (root == nullptr) return 0;
//		int left = _size(root->_left);
//		int right = _size(root->_right);
//		return left + right + 1;
//	}
//	Node* _root=nullptr;
//};
